package com.yhq.basic.algorithm.array;

/**
 * @author hqyin
 * @date 2023/8/23 10:09 上午
 */
public class MyLinkedList<T> {
    private MyNode<T> first;
    private MyNode<T> last;
    private int size;

    public void add(T e) {
        linkLast(e);
    }

    public void add(int index, T e) {
        checkPositionIndex(index);
        if (index == size) {
            linkLast(e);
        } else {
            linkBefore(e, getNode(index));
        }
    }

    private void checkPositionIndex(int index) {
        if (index > size || index < 0) {
            throw new IndexOutOfBoundsException("size=" + size + " ,index=" + index);
        }
    }

    private void checkIndex(int index) {
        if (index >= size || index < 0) {
            throw new IndexOutOfBoundsException("size=" + size + " ,index=" + index);
        }
    }

    public T get(int index) {
        checkIndex(index);
        MyNode<T>  node =getNode(index);
        return node.item;
    }

    private void linkFirst(T e, MyNode<T> nex) {
        MyNode<T> cur = new MyNode<>(e, null, nex);
        first = cur;
        last = cur;
        size++;
    }

    private void linkLast(T e) {
        MyNode<T> pre = last;
        MyNode<T> cur = new MyNode<>(e, pre, null);
        last = cur;
        if(pre == null) {
            first = cur;
        } else {
            pre.next = cur;
        }
        size++;
    }

    private void linkBefore(T e, MyNode<T> next) {
        MyNode<T> pre = next.pre;
        MyNode<T> cur = new MyNode<>(e, pre, next);
        if (pre == null) {
            first = cur;
        } else {
            pre.next = cur;
        }
        next.pre = cur;
        size++;
    }

    private MyNode<T> getNode(int index) {
        int half = size >> 1;
        if (index <= half) {
            MyNode<T> cur = first;
            for(int i = 0;i<index; i++) {
                cur = cur.next;
            }
            return cur;
        } else {
            MyNode<T> cur = last;
            for (int i = size -1; i > index; i--) {
                cur = cur.pre;
            }
            return cur;

        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder("MyLinkedList[");
        int cnt = 0;
        MyNode<T> curNode = first;
        while (cnt < size) {
            sb.append(curNode.item);
            if (cnt != size - 1) {
                sb.append(",");
            }
            curNode = curNode.next;
            cnt++;
        }

        sb.append("]");
        return sb.toString();
    }

    public T remove(T e) {
        MyNode<T> cur = getNode(e);
        if(cur == null) {
            return null;
        } else {
            return unlink(cur);
        }
    }

    private T unlink(MyNode<T> cur) {
        MyNode<T> pre = cur.pre;
        MyNode<T> next = cur.next;
        if(pre == null) {
            first = next;
        } else {
            pre.next = next;
            cur.pre = null;
        }

        if(next == null) {
            last = pre;
        } else {
            next.pre = pre;
            cur.next = null;
        }

        T result = cur.item;
        cur.item = null;
        size --;
        return result;
    }

    private MyNode<T> getNode(T e) {
        MyNode<T> cur = first;
        for (int i = 0; i < size; i++) {
            if(e == null && cur.item == null) {
                return cur;
            } else if(e!= null && e.equals(cur.item)) {
                return cur;
            } else {
                cur = cur.next;
            }
        }
        return null;
    }

    public T remove(int index) {
        checkIndex(index);
        return unlink(getNode(index));
    }

    private static class MyNode<T> {
        T item;
        MyNode<T> pre;
        MyNode<T> next;

        public MyNode(T item, MyNode<T> pre, MyNode<T> next) {
            this.item = item;
            this.pre = pre;
            this.next = next;
        }
    }
}
